package com.yubest;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 *
 *
 * 示例 1：
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * 示例 2：
 *
 * 输入：lists = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：lists = [[]]
 * 输出：[]
 *
 *
 * 提示：
 *
 * k == lists.length
 * 0 <= k <= 10^4
 * 0 <= lists[i].length <= 500
 * -10^4 <= lists[i][j] <= 10^4
 * lists[i] 按 升序 排列
 * lists[i].length 的总和不超过 10^4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/1 16:21
 */
public class P0023 {

    public static void main(String[] args) {
        ListNode[] lists = new ListNode[]{new ListNode(1, new ListNode(4, new ListNode(5))),
                new ListNode(1, new ListNode(3, new ListNode(4))),
                new ListNode(2, new ListNode(6))};
        new Solution23().mergeKLists2(lists);

        new Solution23().mergeKLists(new ListNode[0]);

    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution23 {

    //将所有数放入ArrayList中，然后排序，最后生成ListNode

    //分治合并，两两合并

    /**
     * 思路：参考合并两个有序链表
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        //定义哨兵位
        ListNode guard = new ListNode();
        //定义当前操作的节点
        ListNode cur = guard;
        int min;
        int index = 0;
        Set<Integer> count = new HashSet<>();
        do {
            min = 10001;
            for (int i = 0; i < lists.length; i++) {
                if (null == lists[i]) {
                    count.add(i);
                    continue;
                }
                if (min > lists[i].val) {
                    index = i;
                    min = lists[i].val;
                }
            }
            if (min != 10001) {
                cur.next = new ListNode(min);
                cur = cur.next;
                lists[index] = lists[index].next;
            }
        } while (count.size() != lists.length);

        return guard.next;
    }

    /**
     * 思路：数组下标本身有序，利用数组下标存储元素的值
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        ListNode cur;
        int[] arr = new int[20000 + 1];
        for (ListNode list : lists) {
            cur = list;
            while (cur != null) {
                arr[cur.val + 10000]++;
                cur = cur.next;
            }
        }
        ListNode guard = new ListNode();
        cur = guard;
        for (int i = 0; i < arr.length; i++) {
            while (arr[i]-- > 0) {
                cur.next = new ListNode(i - 10000);
                cur = cur.next;
            }
        }
        return guard.next;
    }

}
